class MinHeap:
    def __init__(self, arr):
        self.capacity = len(arr) + 1
        self.arr = [0] * self.capacity
        self.size = 0
        for i in arr:
            self.insert(i)

    def insert(self, val):
        self.size += 1
        i = self.size
        while self.arr[i / 2] > val:
            self.arr[i] = self.arr[i / 2]
            i /= 2
        self.arr[i] = val

    def pop(self):
        if self.size == 0:
            return None

        result = self.arr[1]
        last = self.arr[self.size]
        self.size -= 1

        i = 1
        while i * 2 <= self.size:
            next_ = i * 2
            if next_ != self.size and self.arr[next_+1] < self.arr[next_]:
                next_ += 1

            if last > self.arr[next_]:
                self.arr[i] = self.arr[next_]
            else:
                break
            i = next_
        self.arr[i] = last
        return result

if __name__ == '__main__':
    heap = MinHeap([1, 3, 5, 4, 2])
    r = 0
    while r is not None:
        r = heap.pop()
        print(r)
